In recent years, distribution of digital contents is becoming active along with diffusion of broadband communication networks, and protection of such contents is an important issue.
The following documents are considered:                [Patent Document 1] Japanese Unexamined Patent Publication No. 2003-289297        [Patent Document 2] Japanese Unexamined Patent Publication No. 2003-273858        [Patent Document 3] Japanese Unexamined Patent Publication No. 2002-123429        [Patent Document 4] Japanese Unexamined Patent Publication No. 11 (1999)-187013        [Non-Patent Document 1] A. Fiat and M. Naor, “Broadcast Encryption,” Crypto '93, Lecture Notes in Computer Science (LNCS) 773, pp. 480-491, 1994        [Non-Patent Document 2] D. Naor, M. Naor, and J. Lotspiech, “Revocation and Tracing Scheme for Stateless Receivers,” Advances in Cryptology—Crypto 2001, Lecture Notes in Computer Science (LNCS) 2139, Springer, pp. 41-62, 2001        [Non-Patent Document 3] Matsuzaki et al, “Tree Structure Key Management Method Supporting Multiple Systems,” SCIS '02, pp. 721-726, 2002        [Non-Patent Document 4] Okuaki et al, “Proposal of a Hybrid System Combining Complete Subtree Method and Subset Difference Method,” SCIS '03, pp. 221-226, 2003        [Non-Patent Document 5] Kim et al., “Broadcast Encryption Schemes Suitable for Half-Rate Revocation,” SCIS '03, pp. 305-309, 2003        [Non-Patent Document 6] Asano, “Efficient Broadcast Encryption Method based on a Key Tree Structure,” SCIS '03, pp. 209-214, 2003        [Non-Patent Document 7] Ogata et al., “Efficient Tree Based Key Management based on RSA function,” SCIS '04, pp. 195-199, 2004        [Non-Patent Document 8] Kikuchi et al., “Modified Subset Difference Method with Reduced Strage of Secret Key at Users,” SCIS '04, pp. 83-87, 2004        [Non-Patent Document 9] Nojima et al., “Tree Based Key Management Using Trapdoor On-Way Functions,” SCIS '03, pp. 131-136, 2003        
As one of techniques for protecting the contents, broadcast encryption (hereinafter abbreviated as BE) which is an encryption method allowing only a receiver selected by a transmitter to decrypt encrypted information is applied to CPRM/CPPM and the like, for example. (See Non-Patent Document 1).
When individual keys are managed for respective decrypting devices in the BE method, the number of keys to be managed will be immense. Moreover, the information encrypted for each decrypting device needs to be included in an encrypted message. Accordingly, a message length of the encrypted message subject to broadcast is increased. To solve such a problem, there is a disclosed method of allocating keys by use of a tree structure. (See Patent Documents 1 to 4 and Non-Patent Documents 2 to 9).
Non-Patent Document 2 discloses typical BE methods applying the tree structure, namely, a complete subtree (hereinafter abbreviated as CS) method and a subset difference (hereinafter abbreviated as SD) method.
In the CS method, each decrypting device is allocated to a leaf (a terminal node) of a complete binary tree, and node keys for the respective nodes ranging from a terminal node to a root node are stored in each device. An encrypting device selects a set of complete subtrees Si, which does not include a decrypting device with the decrypting of a message disabled in a terminal node thereof but includes only decrypting devices enabled to decrypt the message in the terminal nodes. Thereafter, the encrypting device encrypts a message body by use of a title key, then encrypts the title key with one or a plurality of node keys of one or a plurality of nodes respectively located on a vertex or vertices of one or a plurality of selected complete subtrees Si, and then broadcasts the encrypted message including the foregoing information. Upon receipt of the encrypted message, the qualified decrypting device is able to decrypt the title key, which is encrypted with the node key for any of nodes from the terminal node to the root node corresponding to the decrypting device, and thereby to decrypt the message by use of the decrypted title key.
In the CS method, assuming that the number of nodes is N and that the number of decrypting devices with the decrypting of the message disabled (the number of decrypting devices to be disabled) is r, each decrypting device will have a key defined as log N+1. Here, the base of log is k in the case of using a k-th order tree, which is equal to 2 in the case of using a binary tree (hereinafter similarly applicable), for example. Meanwhile, a message length (the number of node keys used for encrypting the title key) will be equal to r*log(N/r) in the worst case.
In the SD method, if one of terminal nodes in a complete subtree having the node as the vertex represents a decrypting device with the decrypting of a message disabled, then a node key is further provided, associated with each of the nodes, for allowing decrypting device in the complete subtree other than the disabled decrypting device to perform decryption.
In the SD method, each decrypting device will have a key defined as ((log N)2+log N)/2+1, and the message length will be equal to 2r−1 in the worst case and 1.25r on average.
Non-Patent Document 4 discloses a method combining the CS method and the SD method. In this method, when N=215, the message length becomes larger than the message length in the SD method. According to Non-Patent Document 5, the message length is almost equal to N/3 when the number of disabled decrypting devices is about half of the total decrypting devices. Non-Patent Document 3 discloses a method of managing a tree structure supporting a plurality of systems by encrypting and publicizing node keys for the tree structure. In this method, an encrypting device publicizes the node keys in the number proportional to the number of nodes.
In the CS method, the number of node keys used for encrypting the title key will increase along with an increase in the number of decrypting devices with the decrypting of the message disabled. As a result, the message length increases. Meanwhile, in the SD method, although it is possible to reduce the message length as compared to the CS method, the number of node keys to be stored by each decrypting device will increase on the contrary. To enhance efficiency of the BE, there is a demand for a method which is capable of significantly reducing the message length while not increasing the number of node keys to be stored by each decrypting device in comparison with the CS method, the SD method, and other conventional techniques.